package com.yangjiayu.algorithm.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class threeSum {

    //方法一：暴力法，穷举所有三数组合 时间复杂度O(n^3)排列组合C3n
    public List<List<Integer>>threeSum(int[] nums) {
        int n = nums.length;
        //定义结果列表
        List<List<Integer>> result = new ArrayList<>();
        //三重for循环，美枚举所有的三数组合
        for(int i = 0;i<n-2;i++){
            for(int j = i+1;j<n-1;j++){
                for(int k = j+1;k<n;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer>list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        //result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                        result.add(list);
                    }
               }
            }
        }
        //甚至还没有进行去重，这并不是最优解
        return result;
    }


    //方法二：用哈希表来做，时间复杂度O(n^2)
    public List<List<Integer>>threeSum2(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();

        //定义一个HashMap
        HashMap<Integer,List<Integer>> map = new HashMap<>();

        //遍历数组，寻找每个数对应的那个数
        for(int i = 0;i<n;i++){
            int thatNum = 0-nums[i];
            if(map.containsKey(thatNum)){
                // 如果以及存在thatNum 就找到了一组解
                ArrayList<Integer> tempList = new ArrayList<>(map.get(thatNum));
                tempList.add(nums[i]);
                result.add(tempList);
            }
            // 把当前数对应的两数组合都保存到map中
            for(int j = 0;j<i;j++){
                //以两数之和作为key
                int newKey = nums[i] + nums[j];
                //如果key不存在 就直接添加进去
                if(!map.containsKey(newKey)){
                    ArrayList<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[j]);
                    map.put(newKey,tempList);
                }
                //问题：如果是 -1 0 ==》 -1  但是-3 2 ==》-1  会产生重复 这种时间复杂度时间复杂度O（n^2）这也不是很好的选择
            }

        }
        return result;
    }


    //方法三：双指针法
    //一个场景 ： 三人篮球队 核心（最矮的）找两个队友 ==》 平均身高1.80
    public List<List<Integer>>threeSum3(int[] nums) {
        int n = nums.length;
        //定义一个结果数组
        List<List<Integer>> result = new ArrayList<>();
        //排序
        java.util.Arrays.sort(nums);
        //遍历数组 挨个当核心
        /*
        -4  -1  -1  0  1  2
        i   L             R
         */
        //0.先对排序
        Arrays.sort(nums);//原地排序
        //1.遍历每一个元素，作为当前三元组中最小的哪个（最矮个做核心）
        for(int i = 0;i<n;i++){
            // 1.1如果当前数已经大于0 直接退出循环
            if(nums[i] > 0)break;

            // 1.2如果当前数据已经出现过，直接跳过
            if(i>0 && nums[i] == nums[i-1]) continue;

            // 1.3 常规情况，以当前数做最小数，定义左右指针
            int lp = i + 1;
            int rp = n - 1;
            // 只要左右指针不重叠，就继续移动指针
            while(lp < rp) {
                int sum = nums[i] + nums[lp] + nums[rp];
                // 判断sum,与0做大小对比
                if(sum == 0){
                    // 1.3.1 等于0 就是找到了一组解
                    result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));
                    // 1.3.2 移动指针，继续寻找
                    lp++;
                    rp--;
                    // 如果移动之后的元素相同 直接跳过
                    while(lp < rp && nums[lp] == nums[lp-1]) lp++;
                    while(lp < rp && nums[rp] == nums[rp+1]) rp--;
                }
                // 1.3.3 小于0 较小的数增大 左指针右移动
                else if(sum < 0){
                    lp++;
                }
                // 1.3.4 大于0 较大的数减小 右指针左移动
                else{
                    rp--;
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] input = {-1,0,1,2,-1,-4};
        threeSum ts = new threeSum();
        List<List<Integer>> result = ts.threeSum3(input);
        for(List<Integer> list:result){
            System.out.println(list);
        }
    }
}
